import java.util.ArrayList;
import java.util.List;

public class FindAllAnagramsInAString {
    // 规则: 窗口大小固定为 字符串p 的长度, 且其元素内容与 字符串p 一致
    // 即 窗口内字符出现的次数和 p中字符出现的次数一样
    public List<Integer> findAnagrams(String s, String p) {
        int n1 = s.length();
        int n2 = p.length();

        char[] ch1 = s.toCharArray();
        char[] ch2 = p.toCharArray();

        // key-字符   value-字符出现的次数
        int[] hash1 = new int[26]; // 模拟哈希表, 字符的 ASCII 码值作为下标
        int[] hash2 = new int[26];
        for(char c : ch2) {
            // 记录 p 各字符出现的次数
            hash2[c - 'a']++;
        }

        int valid = 0; // 记录有效字符个数
        int left = 0, right = 0;

        List<Integer> ret = new ArrayList<>();
        while(right < n1) {
            // 1.进窗口
            char in = ch1[right];
            hash1[in - 'a']++;
            if(hash1[in - 'a'] <= hash2[in - 'a']) {
                // 如果当前字符出现一次后, 依旧小于等于 p 中该字符出现的次数, 说明进入了一个有效字符
                valid++;
            }

            // 2.判断(窗口大小需要固定为 s 的长度)
            while(right - left + 1 == n2) {
                if(valid == n2) {
                    // 窗口size 为 s 长度, 且窗口有效字符能全部对上 s, 更新结果
                    ret.add(left);
                }

                // 3.出窗口
                char out = ch1[left];
                hash1[out - 'a']--;
                if(hash1[out - 'a'] < hash2[out - 'a']) {
                    valid--;
                }
                left++;
            }

            right++;
        }
        return ret;
    }
}
